In [143]:
# LinkedList Node
class LLNode:
    def __init__(self, value):
        self.next = None
        self.value = value
    
    def __str__(self):
        node = self
        string = "Linked List:"
        while node != None:
            string = "{0} {1}".format(string, node.value)
            node = node.next
        return string
    
    def append(self, value):
        node = self
        while node.next != None:
            node = node.next
        node.next = LLNode(value)

def delete(head, value):
    curr = head
    if curr.value == value:
        head = curr.next
        curr = None
        return head
    
    while curr.next != None:
        if curr.next.value == value:
            curr.next = curr.next.next
            return head
        curr = curr.next
    return head

In [144]:
# Simple LinkedList implementation
linked_list = LLNode(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(2)

print(linked_list)
delete(linked_list, 2)
print(linked_list)


Linked List: 1 2 3 2
Linked List: 1 3 2

2.1

Write code to remove duplicates from an unsorted linked list.

FOLLOW UP - How would you solve this problem if a temporary buffer is not allowed?


In [145]:
def remove_duplicates(linked_list):
    nodes_seen = set()
    prev = None
    curr = linked_list
    while curr != None:
        if curr.value in nodes_seen:
            prev.next = curr.next
        else:
            nodes_seen.add(curr.value)
            prev = curr
        curr = curr.next

In [146]:
llist = LLNode(1)
llist.append(4)
llist.append(5)
llist.append(5)
llist.append(5)
llist.append(1)
llist.append(6)
llist.append(5)
llist.append(3)
print(llist)
remove_duplicates(llist)
print(llist)


Linked List: 1 4 5 5 5 1 6 5 3
Linked List: 1 4 5 6 3

In [147]:
def remove_duplicates_followup(linked_list):
    curr = linked_list
    while curr != None:
        ahead = curr
        while ahead.next != None:
            if curr.value == ahead.next.value:
                ahead.next = ahead.next.next
            else:
                ahead = ahead.next
        curr = curr.next

In [148]:
llist = LLNode(1)
llist.append(4)
llist.append(5)
llist.append(5)
llist.append(5)
llist.append(1)
llist.append(6)
llist.append(5)
llist.append(3)
print(llist)
remove_duplicates_followup(llist)
print(llist)


Linked List: 1 4 5 5 5 1 6 5 3
Linked List: 1 4 5 6 3

2.2

Implement an algorithm to find the kth to last element of a singly linked list.


In [149]:
def find_kth_last(linked_list, k):
    if k < 0:
        return None
    curr = linked_list
    runner = linked_list.next
    for i in range(1, k):
        if runner == None:
            if i == k:
                return curr
            else:
                return None
        runner = runner.next
    while runner != None:
        curr, runner = curr.next, runner.next
    return curr

In [150]:
llist = LLNode(1)
llist.append(4)
llist.append(5)
llist.append(5)
llist.append(5)
llist.append(1)
llist.append(6)
llist.append(5)
llist.append(3)
print(llist)
node = find_kth_last(llist, 3)
print(node)


Linked List: 1 4 5 5 5 1 6 5 3
Linked List: 6 5 3

2.3

Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.

EXAMPLE

Input: the node c from the linked list a->b->c->d->e

Result: nothing is returned but the new linked list looks like a->b->d->e


In [151]:
def remove_from_middle(node):
    if (node == None) or (node.next == None):
        return False
    node.value = node.next.value
    node.next = node.next.next

In [152]:
llist = LLNode(1)
llist.append(4)
llist.append(5)
llist.append(5)
llist.append(5)
llist.append(1)
llist.append(6)
llist.append(5)
llist.append(3)
print(llist)
node = llist.next.next.next.next.next
print(node)
remove_from_middle(node)
print(llist)


Linked List: 1 4 5 5 5 1 6 5 3
Linked List: 1 6 5 3
Linked List: 1 4 5 5 5 6 5 3